package astudy.tree.impl;

import astudy.tree.Tree;
import astudy.tree.TreeNode;
import astudy.util.Indent;

/**
 * Binary Search tree
 * @author wong tong
 *
 * @param <T>
 */
public class BSTree<T extends Comparable> implements Tree<T> {
	
	private BSTreeNode<T> root;
	
	public BSTree() {
		
	}

	public void delete(TreeNode<T> node) {

		BSTreeNode<T> r = (BSTreeNode<T>)node;
		if (r.getLeft() == null || r.getRight() == null) {
			if (r.getLeft() != null) {
				r.getParent().setLeft(r.getLeft());
				r.getLeft().setParent(r.getParent());
			} else if (r.getRight() != null) {
				r.getParent().setRight(r.getRight());
				r.getRight().setParent(r.getParent());
			}
			r = null;
		} else {
			BSTreeNode<T> next = (BSTreeNode<T>)this.next(r);
			r.setData(next.getData());
			delete(next);
		}
		
	}

	@SuppressWarnings("unchecked")
	public TreeNode<T> find(TreeNode<T> root, T data) {
		
		BSTreeNode<T> r = (BSTreeNode<T>)root;
		while (r != null) {
			int compare = r.getData().compareTo(data);
			if (compare == 0) {
				return r;
			} else if (compare > 0) {
				r = r.getLeft();
			} else {
				r = r.getRight();
			}
		}
		return null;
	}

	@SuppressWarnings("unchecked")
	public void insert(TreeNode<T> node) {

		if (this.root == null) {
			this.root = (BSTreeNode<T>)node;
		} else {
			BSTreeNode<T> n = (BSTreeNode<T>)node;
			BSTreeNode<T> cursor = this.root;
			while (cursor != null) {
				if (cursor.getData().compareTo(n.getData()) >= 0) {
					if (cursor.getLeft() == null) {
						cursor.setLeft(n);
						n.setParent(cursor);
					} else {
						cursor = cursor.getLeft();
						continue;
					}
				} else {
					if (cursor.getRight() == null) {
						cursor.setRight(n);
						n.setParent(cursor);
					} else {
						cursor = cursor.getRight();
						continue;
					}
				}
			}
		}
		
	}

	public TreeNode<T> max(TreeNode<T> root) {

		BSTreeNode<T> r = (BSTreeNode<T>)root;
		if (r == null) {
			return null;
		} else {
			while (r.getRight() != null) {
				r = r.getRight();
			}
			return r;
		}
	}

	public TreeNode<T> min(TreeNode<T> root) {

		BSTreeNode<T> r = (BSTreeNode<T>)root;
		if (r == null) {
			return null;
		} else {
			while (r.getLeft() != null) {
				r = r.getLeft();
			}
			return r;
		}
	}

	public TreeNode<T> next(TreeNode<T> node) {

		BSTreeNode<T> r = (BSTreeNode<T>)node;
		if (r.getRight() != null) {
			return min(r.getRight());
		} else {
			BSTreeNode<T> c = r;
			r = r.getParent();
			while (r != null && r.getRight() == c) {
				c = r;
				r = r.getParent();
			}
			return r;
		}
	}

	public TreeNode<T> prev(TreeNode<T> node) {

		BSTreeNode<T> r = (BSTreeNode<T>)node;
		if (r.getLeft() != null) {
			return max(r.getLeft());
		} else {
			BSTreeNode<T> c = r;
			r = r.getParent();
			while (r != null && r.getLeft() == c) {
				c = r;
				r = r.getParent();
			}
			return r;
		}
	}

	@Override
	public String toString() {

		Indent indent = new Indent();
		return string(this.root, indent);
	}
	
	private String string(BSTreeNode<T> root, Indent indent) {
		
		String str = "";
		if (root == null) {
			str = "NIL\n";
		} else {
			str = root.getData() + "\n";
			indent.increase();
			str += indent + string(root.getLeft(), indent);
			str += indent + string(root.getRight(), indent);
			indent.decrease();
		}
		return str;
	}
}
